﻿#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
private:
    int m, n, k;
    bool visited[101][101];
    int dfs(int i, int j) {
        if (getDigitSum(i, j) > k || visited[i][j]) return 0;
        visited[i][j] = true;
        int ans = 0;
        if (i > 0) ans += dfs(i - 1, j);
        if (i < m - 1) ans += dfs(i + 1, j);
        if (j > 0) ans += dfs(i, j - 1);
        if (j < n - 1) ans += dfs(i, j + 1);
        return ans + 1;
    }
    int getDigitSum(int i, int j) {
        int si = i % 10 + (i / 10) % 10 + (i / 100) % 10;
        int sj = j % 10 + (j / 10) % 10 + (j / 100) % 100;
        return si + sj;
    }
public:
    int movingCount(int m, int n, int k) {
        this->m = m;
        this->n = n;
        this->k = k;
        memset(this->visited, 0, sizeof(visited));
        return dfs(0, 0);
    }
};

int main() {
    Solution solution;
    int m = 11, n = 8, k = 15;
    cout << solution.movingCount(m, n, k) << endl;
    return 0;
}